Analysis of and workarounds for element reversal for a finite element-based algorithm for warping triangular and tetrahedral meshes

摘要

We consider an algorithm called FEMWARP for warping triangular andtetrahedral finite element meshes that computes the warping using the finiteelement method itself. The algorithm takes as input a two- or three-dimensionaldomain defined by a boundary mesh (segments in one dimension or triangles intwo dimensions) that has a volume mesh (triangles in two dimensions ortetrahedra in three dimensions) in its interior. It also takes as input aprescribed movement of the boundary mesh. It computes as output updatedpositions of the vertices of the volume mesh. The first step of the algorithmis to determine from the initial mesh a set of local weights for each interiorvertex that describes each interior vertex in terms of the positions of itsneighbors. These weights are computed using a finite element stiffness matrix.After a boundary transformation is applied, a linear system of equations basedupon the weights is solved to determine the final positions of the interiorvertices. The FEMWARP algorithm has been considered in the previous literature(e.g., in a 2001 paper by Baker). FEMWARP has been succesful in computingdeformed meshes for certain applications. However, sometimes FEMWARP reverseselements; this is our main concern in this paper. We analyze the causes forthis undesirable behavior and propose several techniques to make the methodmore robust against reversals. The most successful of the proposed methodsincludes combining FEMWARP with an optimization-based untangler.